#include <iostream>
#include <cstring>
using namespace std;

const int N = 100010;
const int INF = 0x3f3f3f3f;

int n;
int a[N];
int f[N], cnt = 1; //这里f[i]代表的意思是长度为i的上升子序列的最小尾数，迭代n次后就能取得真实的数据
//cnt设置为1，是因为f[1]会默认初始化

int find(int x, int l = 1, int r = cnt) //在1~cnt这个区间内找到第一个大于a[i]的数据的下标
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (f[mid] >= x)
            r = mid;
        else
            l = mid + 1;
    }
    return l;
}

int main()
{
    freopen("cin.txt", "r", stdin);
    memset(f, 0x3f, sizeof f); //一开始将f全部设置为极大值，方便后面更新
    cin >> n;
    for (int i = 1; i <= n; ++i) //还是从1开始吧，防止边缘值，不过这个貌似没啥边缘值可以防的
    {
        cin >> a[i];
        if (f[1] >= a[i]) //第一种情况
            f[1] = a[i];
        else if (f[cnt] < a[i]) //第三种情况
            f[++cnt] = a[i];
        else                      //第三种情况
            f[find(a[i])] = a[i]; //找到该找的位置，并且更新
    }
    cout << cnt;
}